package _06_deque.my_implements;

import _06_deque.Deque;

import java.util.Iterator;
import java.util.StringJoiner;

/**
 * @author: mornd
 * @dateTime: 2023/6/7 - 21:02
 * "循环"数组实现双端队列
 * tail 单独占用数组一个空位
 */
public class ArrayDeque<E> implements Deque<E>, Iterable<E> {
    E[] data;
    int head;
    int tail;
    int capacity;

    public ArrayDeque(int capacity) {
        data = (E[]) new Object[this.capacity = capacity + 1]; // +1 表示 tail
    }

    /**
     * 参考 jdk ArrayDeque 实现
     *
     * @param i
     * @return
     */
    int inc(int i) {
        if (++i >= capacity) {
            i = 0;
        }
        return i;
    }

    int dec(int i) {
        if (--i < 0) {
            i = capacity - 1;
        }
        return i;
    }

    /*
        2
        t     h
        0  1  2
     */
    @Override
    public boolean offerFirst(E e) {
        if (isFull()) {
            return false;
        }
        head = dec(head);
        data[head] = e;
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        if (isFull()) {
            return false;
        }
        data[tail] = e;
        tail = inc(tail);
        return true;
    }

    /*
        2
           h  t
        0  1  2
     */
    @Override
    public E popFirst() {
        if (isEmpty()) {
            return null;
        }
        E e = data[head];
        data[head] = null;
        head = inc(head);
        return e;
    }

    @Override
    public E popLast() {
        if (isEmpty()) {
            return null;
        }
        tail = dec(tail);
        E e = data[tail];
        data[tail] = null;
        return e;
    }

    @Override
    public E peekFirst() {
        if (isEmpty()) {
            return null;
        }
        return data[head];
    }

    @Override
    public E peekLast() {
        if (isEmpty()) {
            return null;
        }
        return data[dec(tail)];
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    /*
        2
        t  h
        0  1  2
     */
    @Override
    public boolean isFull() {
        if (head > tail) {
            return head - 1 == tail;
        } else if (head < tail) {
            return tail - head == capacity - 1;
        } else {
            return false;
        }
    }

    @Override
    public Iterator<E> iterator() {
        /*
        t  h
        0  1  2
        */

        return new Iterator<E>() {
            int i = head;

            @Override
            public boolean hasNext() {
                return i != tail;
            }

            @Override
            public E next() {
                E e = data[i];
                i = inc(i);
                return e;
            }
        };
    }

    @Override
    public String toString() {
        StringJoiner joiner = new StringJoiner(",", "[", "]");
        for (E e : this) {
            joiner.add(String.valueOf(e));
        }
        return joiner.toString();
    }
}
